package pt.ipbeja.estig.eda;

public class MergeSort
{
   int[] array;
   
   public MergeSort( int[] array )
   {
      this.array = array;
   }

   /**
    * Merge Sort Constructor 
    * @param p Array index
    * @param r Array index
    */
   public void sort( int p, int r )
   {
      if ( p < r )
      {
         int q = ( p + r ) / 2;
   
         this.sort( p, q );
         this.sort( q + 1, r );
         this.mergeSort( p, q ,r );
      }
   }
   
   /**
    * Merge Sort Method 
    * @param p Array index
    * @param q Array index
    * @param r Array index
    */
   private void mergeSort( int p, int q, int r )
   {
      int n1 = q - p + 1;
      int n2 = r - q;
   
      int[] L = new int[ n1 + 1 ];
      int[] R = new int[ n2 + 1 ];
   
   
      for( int i = 0; i < n1; i++ )
      {
         L[ i ] = this.array[ p + i ];
      }
      L[ n1 ] =  Integer.MAX_VALUE;
   
      for ( int j = 0; j < n2; j++ )
      {
         R[ j ] = this.array[ q + j + 1 ];
      }
      R[ n2 ] =  Integer.MAX_VALUE;
   
      int i = 0;
      int j = 0;
   
      for( int k = p; k < r + 1; k++ )
      {
         if( L[ i ] < R[ j ] )
         {
            this.array[ k ] = L[ i ];
            i++;
         }
         else
         {
            this.array[ k ] = R[ j ];
            j++;
         }
      }
   }
}